#include <dbg.h>

#include <cassert>

using namespace std;

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int res = 1;
        int left = 0;
        long long total = 0;
        for (int right = 1; right < n; ++right) {
            total +=
                (long long)(nums[right] - nums[right - 1]) * (right - left);
            while (total > k) {
                total -= nums[right] - nums[left];
                ++left;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};

int main() {
    Solution s;

    vector<int> nums1 = {1, 2, 4};
    vector<int> nums2 = {1, 4, 8, 13};
    vector<int> nums3 = {3, 9, 6};
    vector<int> nums4 = {100000};

    int k1 = 5;
    int k2 = 5;
    int k3 = 2;
    int k4 = 100000;

    assert(s.maxFrequency(nums1, k1) == 3);
    assert(s.maxFrequency(nums2, k2) == 2);
    assert(s.maxFrequency(nums3, k3) == 1);
    assert(s.maxFrequency(nums4, k4) == 1);

    return 0;
}